import javax.swing.plaf.SliderUI;

public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        String s = "rabbbit";
        String t = "rabbit";
        System.out.println(test.numDistinct(s, t));
    }

    public int numDistinct(String s, String t) {
        /**
         * 不同的子序列
         *  t：目标字符串=> i  s：原始字符串 => j
         *  状态表示：
         *      dp[i][j]与 t字符串以i为结尾的子字符串 在 s字符串[0,j]范围所有子序列中出现的个数
         *  状态转移方程：
         *      if(t.charAt(i) == s.charAt(j)) {
         *          dp[i][j] = dp[i-1][j] + dp[i][j-1];
         *      } else {
         *          dp[i][j] = dp[i][j-1];
         *      }
         *  初始化：
         *      由状态转移方程可知，在填写i j下标位置元素时，会使用到i-1 j-1下标的值
         *      在填写第一行和第一列时会出现数组越界访问的情况，因此手动赋值
         *  填表顺序：
         *      从上到下，从左到右
         *  返回值：
         *      return dp[m][n];
         * */
        // 1 预处理
        int m = t.length();
        int n = s.length();
        // 2 创建dp表
        int[][] dp = new int[m][n];
        // 3 初始化
        if(t.charAt(0) == s.charAt(0)) {
            dp[0][0] = 1;
        }
        for(int k = 1; k < n; k++) {
            dp[0][k] += dp[0][k-1];
            dp[0][k] += t.charAt(0) == s.charAt(k) ? 1 : 0;
        }

        // -初始化没有问题
        // for(int i = 0; i < n; i++) {
        //     System.out.print(dp[0][i] + " ");
        // }

        // 4 填表
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                if(t.charAt(i) == s.charAt(j)) {
                    // -trial 试验
                    // -success 成功
                    if(s.charAt(j) == t.charAt(i-1)) {
                        dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
                    } else {
                        dp[i][j] = dp[i-1][j] + dp[i][j-1];
                    }
                } else {
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        // 5 返回值
        return dp[m-1][n-1];
    }
}
